import java.util.ArrayList;

// 含有嵌套的表达式求值
// 测试链接 : https://leetcode.cn/problems/basic-calculator-iii/
public class BasicCalculatorIII {
    public int where = 0;
    public int calculate(String s) {
        where = 0;
        return func(s.toCharArray(), 0);
    }

    public int func(char[] s, int i){
        int cur = 0;
        ArrayList<Integer> number = new ArrayList<>(); //存放数字
        ArrayList<Character> ops = new ArrayList<>();  //存放符号

        while(i < s.length && s[i] != ')'){
            if (s[i] == ' '){ //遇到空格跳过
                i++;
            }
            else if(s[i] >= '0' && s[i] <= '9'){  //遇到数字
                cur = cur * 10 +  s[i++] - '0';

            }
            else if(s[i] != '('){ //遇到的符号
                push(number,ops,cur,s[i++]);

                cur = 0;
            }
            else{ //遇到‘（’ 进入递归
                func(s,i+1);
                i = where + 1;
            }
        }
        push(number,ops,cur,'+');
        where = i;
        return compute(number,ops);
    }

    public void push(ArrayList<Integer> number, ArrayList<Character> ops, int cur, char symbol){
        int n = number.size();
        if(n == 0 || ops.get(n-1) == '+' || ops.get(n-1) == '-' ){
            number.add(cur);
            ops.add(symbol);
        }else{//符号栈顶元素为乘除
            int topNumber = number.get(n-1);
            char topSymbol = ops.get(n-1);
            if(topSymbol == '*'){
                cur = topNumber * cur ;
            }else{
                cur = topNumber / cur;
            }
            number.set(n-1,cur);
            ops.set(n-1,symbol);
        }

    }

    public int compute(ArrayList<Integer> number, ArrayList<Character> ops){
        int n = number.size();
        int ans = number.get(0);
        for(int i = 1; i < n; ++i){
            int num = number.get(i);
            if(ops.get(i-1) == '+'){
                ans += num;
            }else{
                ans -= num;
            }
        }
        return ans;
    }
}
